#include "list.h"

#include <assert.h>
#include <stdlib.h>

struct _listnode {
    struct _listnode *left;
    struct _listnode *right;
    void *data; //数据
};
//列表的实现
struct _list{
    ListNode *head;
    ListNode *end;
    int length;
    void *(*listMalloc)(size_t size);
    void (*listFree)(void *ptr);
}
;
struct _listcursor{
	ListNode *pnode;
};

List *ListInit()
{
	List *list;
        list=(List*)malloc(sizeof(List));
    list->length=0;
    list->head=0;
    list->end=0;
    list->listFree=free;
    list->listMalloc=malloc;
    return list;
}

void *ListEnd(List *plist)
{
	assert(plist);
	if(plist->end==0){
		return 0;
	}
	return plist->end->data;
}

void *ListHead(List *plist)
{
	assert(plist);
	if(plist->head==0){
		return 0;
	}
	return plist->head->data;
}

//从末尾操作插入
void *ListPush(List *plist,void *data)
{
    //插入一个节点
    assert(plist);
    assert(data);

    ListNode *pnode;
    pnode=(ListNode*)(plist->listMalloc(sizeof(ListNode)));
    pnode->data=data;
    pnode->left=plist->end;
    pnode->right=0;
    if(plist->end){
        plist->end->right=pnode;
    }else{
    	plist->head=pnode;
    }
    plist->end=pnode;
    plist->length++;
    return pnode->data;
}
void *ListPop(List *plist)
{
	assert(plist);
	if(plist->length==0){
		return 0;
	}
	ListNode *pnode;
	pnode=plist->end;
	plist->end=plist->end->left;
	if(plist->end==0){
		plist->head=0;
	}else{
		plist->end->right=0;
	}
	void *pdata;
	pdata=pnode->data;
	pnode->left=0;
	pnode->right=0;
	plist->listFree(pnode);
	plist->length--;
	return pdata;
}
//从前端操作插入
void *ListImport(List *plist,void *data)
{
    //插入一个节点
    assert(plist);
    assert(data);
    ListNode *pnode;
    pnode=(ListNode*)(plist->listMalloc(sizeof(ListNode)));
    pnode->data=data;
    pnode->right=plist->head;
    pnode->left=0;
    if(plist->head){
        plist->head->left=pnode;
    }else{
    	plist->end=pnode;
    }
    plist->head=pnode;
    plist->length++;
    return pnode->data;
}
void *ListExport(List *plist)
{
	assert(plist);
	if(plist->length==0){
		return 0;
	}
	ListNode *pnode;
	pnode=plist->head;
	plist->head=plist->head->right;
	if(plist->head==0){
		plist->end=0;
	}else{
		plist->head->left=0;
	}
	pnode->left=0;
	pnode->right=0;
	plist->length--;
	void *pdata;
	pdata=pnode->data;
	plist->listFree(pnode);
	return pdata;
}
//任意位置操作
void *ListInsert(List *plist,void *data,ListCursor *pcursor)
{
	assert(plist);
	assert(data);
	if(pcursor==0){
		return ListImport(plist,data);
	}
	if(pcursor->pnode==0){
		return ListImport(plist,data);
	}
	if(pcursor->pnode->left==0){
		pcursor->pnode=0;
		return ListImport(plist,data);
	}
	if(pcursor->pnode->right==0){
		ListPush(plist,data);
		pcursor->pnode=plist->end;
		return plist;
	}
	ListNode *pnode;
	pnode=(ListNode*)(plist->listMalloc(sizeof(ListNode)));
	pnode->data=data;
	pnode->left=pcursor->pnode;
	pnode->right=pcursor->pnode->right;
	pcursor->pnode->right->left=pnode;
	pcursor->pnode->right=pnode;
	pcursor->pnode=pnode;
	plist->length++;
	return pnode->data;
}

void *ListRemove(List *plist,void *data)
{
	assert(plist);
	assert(data);
	if(plist->length==0){
		return 0;
	}
	ListNode *pnode;
	pnode=plist->head;
	while(pnode){
		if(pnode->data==data){
			//删除该数据
			if(pnode->left==0){
				return ListExport(plist);
			}
			if(pnode->right==0){
				return ListPop(plist);
			}
			pnode->left->right=pnode->right;
			pnode->right->left=pnode->left;
			pnode->left=0;
			pnode->right=0;
			plist->listFree(pnode);
			plist->length--;
			return data;
		}
		pnode=pnode->right;
	}
	return 0;


}
void *ListCursorRemove(List *plist,ListCursor *pcursor)
{
	assert(plist);
	assert(pcursor);
	if(plist->length==0){
		return 0;
	}
	if(pcursor->pnode==0){
		return ListExport(plist);
	}
	if(pcursor->pnode->left==0){
		return ListExport(plist);
	}
	if(pcursor->pnode->right==0){
		return ListPop(plist);
	}
	pcursor->pnode->left->right=pcursor->pnode->right;
	pcursor->pnode->right->left=pcursor->pnode->left;
	void *pdata;
	ListNode *pnode;
	pdata=pcursor->pnode->data;
	pnode=pcursor->pnode;
	pcursor->pnode=pcursor->pnode->right;
	pnode->left=0;
	pnode->right=0;
	plist->listFree(pnode);
	plist->length--;
	return pdata;
}
List *ListEmpty(List *plist)
{
	assert(plist);
	while(plist->length){
		ListPop(plist);
	}
	plist->end=0;
	plist->head=0;
	plist->length=0;
	return plist;
}

int ListLength(List *plist)
{
    assert(plist);
    return plist->length;
}

void *ListForeach(List *plist,ListCursor *pcursor)
{
	assert(plist);
	assert(pcursor);

	if(pcursor->pnode==0){
		pcursor->pnode=plist->head;
		if(pcursor->pnode){
				return pcursor->pnode->data;
			}
		return 0;
	}
	pcursor->pnode=pcursor->pnode->right;
	if(pcursor->pnode){
		return pcursor->pnode->data;
	}
	return 0;
}

void ListCursorBack(List *plist,ListCursor *pcursor)
{
	assert(plist);
	assert(pcursor);
	if(pcursor->pnode==0){
		pcursor->pnode=plist->end;
	}
	pcursor->pnode=pcursor->pnode->left;
}

void ListAllocator(List *plist,void *(*pmalloc)(size_t size),void (*pfree)(void *pdata))
{
	assert(plist);
	plist->listMalloc=pmalloc;
	plist->listFree=pfree;
}

ListCursor *ListGetCursor(List *plist)
{
	assert(plist);
	ListCursor *pcursor;
	pcursor=(ListCursor*)malloc(sizeof(ListCursor));
	pcursor->pnode=0;
	return pcursor;
}
